package offerbook;

import java.util.Arrays;

/**
 * Created at 2019/10/28 0028 下午 3:04
 * 把只包含 【质因子】2、3和5的数称作丑数（Ugly Number）。
 * 例如6、8都是丑数，但14不是，因为它包含质因子7。
 * 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
 * <p>
 * 方式1：对每个数都进行丑数判断，时间O(n²)
 * <p>
 * 方式2：利用丑数特性，时间O(n),空间O(n),利用空间记录当前丑数。空间换时间
 */
public class Code34_UglyNumber {

    /**
     * 时间复杂度o(n²),OJ测试时间不过
     */
    public static int getNUglyNumber(int n) {
        if (n <= 0) {
            return 0;
        }
        int res = 0;
        for (int i = 1;;i++) {
            if (isUglyNum(i)) {
                res++;
            }
            if (res == n) return i;
        }
    }

    /**
     * 丑数能够分解成2^x3^y5^z,
     * 所以只需要把得到的丑数不断地乘以2、3、5之后并放入他们应该放置的位置即可，
     * 而此题的难点就在于如何有序的放在合适的位置。
     * 1乘以（2、3、5）=2、3、5；
     * 2乘以（2、3、5）=4、6、10；
     * 3乘以（2、3、5）=6,9,15；
     * 5乘以（2、3、5）=10、15、25；
     * <p>
     * 开启一个数组help，开始记录最初丑数1，
     * 定义三个指针p2,p3,p5表示当前位置的数值*2,*3,*5并没有被使用过。
     * 令 res[i] = Math.min(res[p2]*2,Math.min(res[p3]*3,res[p5]*5));
     * 判断是谁相乘得到的，就让对应的p指针+1.表示已经被消耗过了。
     */
    public static int getNUglyNumber1(int n) {
        if (n <= 0) {
            return 0;
        }
        int[] res = new int[n];
        //1是丑数
        res[0] = 1;
        //每个位置维护三个指针，表示当前位置没有乘过这个数
        int p2 = 0;
        int p3 = 0;
        int p5 = 0;
        for (int i = 1; i < n; i++) {
            //选取各自位置*2,*3,*5后的最小值
            res[i] = Math.min(res[p2] * 2, Math.min(res[p3] * 3, res[p5] * 5));
            //看是哪个数乘得到的，把这个数对应的索引+1，防止重复
            if (res[p2] * 2 == res[i])
                p2++;
            if (res[p3] * 3 == res[i])
                p3++;
            if (res[p5] * 5 == res[i])
                p5++;
        }
        System.out.println(Arrays.toString(res));
        return res[n - 1];
    }

    /**
     * getNUglyNumber1的优化，
     * 由于res数组更新的丑数的有序的，假设当前更新到的位置是j，p2指向的位置是i，
     * res[p2]*2*2*2*...*2可能一直小于res[j],直到有一个位置k，res[p2]*2...*2>res[j],
     * 让p2记录当前为值k即可。
     */
    public static void getNUglyNumber2(int n) {
        if (n <= 0) {
            return;
        }
        int[] res = new int[n];
        //1是丑数
        res[0] = 1;
        //每个位置维护三个指针，表示当前位置没有乘过这个数
        int p2 = 0;
        int p3 = 0;
        int p5 = 0;
        for (int i = 1; i < n; i++) {
            //选取各自位置*2,*3,*5后的最小值
            res[i] = Math.min(res[p2] * 2, Math.min(res[p3] * 3, res[p5] * 5));
            //看是哪个数乘得到的，把这个数对应的索引+1，防止重复
            while (res[p2] * 2 <= res[i])
                p2++;
            while (res[p3] * 3 <= res[i])
                p3++;
            while (res[p5] * 5 <= res[i])
                p5++;
        }
        System.out.println(Arrays.toString(res));
    }

    //判断一个数是不是丑数, 规定1是丑数
    private static boolean isUglyNum(int n) {
        if (n <= 0) {
            return false;
        }
        while (n % 2 == 0) {
            n = n / 2;
        }
        while (n % 3 == 0) {
            n = n / 3;
        }
        while (n % 5 == 0) {
            n = n / 5;
        }
        //1也是丑数
        return n == 1;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        // 1.088s
//        getNUglyNumber(1000);
        //4ms
        getNUglyNumber1(10);
//        getNUglyNumber2(10);

        System.out.println("(System.currentTimeMillis() - start) = " + (System.currentTimeMillis() - start));

    }

}
